package com.swjd.linkedlist;

import com.sun.org.apache.bcel.internal.generic.NEW;

/**
 * 环形链表
 *
 * @author 刘涛
 * @create 2021/9/23 23:05
 */
public class Josepfu {
    public static void main(String[] args) {
        //测试环形链表
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.add(5);//加入5个小孩
        circleSingleLinkedList.showBoy();
        circleSingleLinkedList.countBoy(1,2,5);
    }
}

//创建一个环形的单向链表
class CircleSingleLinkedList {
    //创建一个first节点,目前没有编号
    private Boy first = null;

    /**
     * 添加小孩节点，构建环形链表
     *
     * @param nums 传入要添加的个数
     */
    public void add(int nums) {
        //校验
        if (nums < 1) {
            System.out.println("nums的值不正确!");
            return;
        }
        //辅助指针 永远指向最后一个节点
        Boy curBoy = null;
        //使用for循环创建环形链表
        for (int i = 1; i <= nums; i++) {
            //根据编号创建小孩节点 boy代表要添加的节点
            Boy boy = new Boy(i);
            //如果是第一个小孩
            if (i == 1) {
                first = boy;//添加第一个节点的时候，就是首节点
                first.setNext(first);//第一个节点指向自己 构成环状
                curBoy = first; //curBoy永远指向最后一个节点，当只有第一个节点时，指向第一个节点
            } else {
                curBoy.setNext(boy);//curBoy指针永远指向最后一个节点 当添加一个节点的时候，将curBoy的next指向它
                boy.setNext(first);//将新增节点的next指向首节点，构成环状
                curBoy = boy;//让curBoy指针永远指向最后一个节点
            }
        }
    }

    /**
     * 遍历环形链表
     */
    public void showBoy() {
        //判断链表是否为空
        if (first == null) {
            System.out.println("链表为空！");
            return;
        }
        //辅助指针 指向遍历到的值
        Boy curBoy = first;
        while (true) {
            System.out.println("小孩的编号为：" + curBoy.getNo());
            if (curBoy.getNext() == first) {
                //要遍历的节点的下一个指向首节点，代表已经遍历完成了
                break;
            }
            curBoy = curBoy.getNext();
        }
    }

    /**
     * 小孩出圈顺序
     *
     * @param startNo  表示从第几个小孩开始数数
     * @param countNum 表示数几下
     * @param nums     表示最初有多少个小孩
     */
    public void countBoy(int startNo, int countNum, int nums) {
        //先对数据进行校验
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("参数输入有误，请重新输入");
            return;
        }
        //创建辅助指针 指向最后一个节点
        Boy helper = first;
        while (true) {
            if (helper.getNext() == first) {
                //说明helper已经指向最后一个节点
                break;
            }
            helper = helper.getNext();
        }
        //报数前，先让first指针移动到需要从第startNo个小孩 helper指针跟随移动
        for (int i = 1; i < startNo; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        while (true){
            if (helper == first){
                //圈中只剩一人
                break;
            }
            //移动countNum次
            for (int i = 1; i < countNum; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.println("出圈小孩编号："+first.getNo());
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后留在圈中的小孩是："+first.getNo());
    }

}

//创建一个Boy类，表示一个节点
class Boy {
    private int no;//编号
    private Boy next;//指向下一个节点

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                ", next=" + next +
                '}';
    }
}
